/*****************************************************************************
 *  ENTROPY - emerging network to reduce orwellian potency yield
 *
 *  Copyright (C) 2002 Juergen Buchmueller <pullmoll@stop1984.com>
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software Foundation,
 *  Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
 *
 *	$Id: store_tree.c,v 1.7 2005/07/22 01:52:07 pullmoll Exp $
 *****************************************************************************/
#include "osd.h"
#include "config.h"
#include "store.h"
#include "file.h"
#include "logger.h"

/*
 *	As long as the store drop FIFO is always filled with entries of
 *	the same timeout, we do not need to sort the list before commiting
 *	the deletes.
 */
#define	STORE_QSORT	0

/*
 *	The previous behavior was to chdir() into a store directory before
 *	opening a file, because someone claimed - ages ago - that ought to
 *	be faster than stat() or open() a file with full pathname.
 *	I don't trust this claim, and if you do, you can enable the old
 *	method by defining this to 1.
 */
#define	TREE_CHDIR	0

int store_path(const sha1_digest_t *sha1, char *path, size_t len, size_t *ptree)
{
	uint8_t tree1, tree2, tree3;
	size_t tree, plen;
	FUN("store_path");

	switch (g_conf->storedepth) {
	case 1:
		/* 1 level tree index */
		tree1 = sha1->digest[SHA1SIZE-2] / 16;
		tree = tree1;
		plen = pm_snprintf(path, len, "%s/%x",
			g_conf->storepath, tree1);
		break;
	case 2:
		/* 2 level tree index */
		tree1 = sha1->digest[SHA1SIZE-2] / 16;
		tree2 = sha1->digest[SHA1SIZE-2] % 16;
		tree = (tree1 << 4) | tree2;
		plen = pm_snprintf(path, len, "%s/%x/%x",
			g_conf->storepath, tree1, tree2);
		break;
	case 3:
		/* 2 level tree index */
		tree1 = sha1->digest[SHA1SIZE-2] / 16;
		tree2 = sha1->digest[SHA1SIZE-2] % 16;
		tree3 = sha1->digest[SHA1SIZE-1] / 16;
		tree = (tree1 << 8) | (tree2 << 4) | tree3;
		plen = pm_snprintf(path, len, "%s/%x/%x/%x",
			g_conf->storepath, tree1, tree2, tree3);
		break;
	default:
		tree = 0;
		plen = pm_snprintf(path, len, "%s", g_conf->storepath);
	}

#if	TREE_CHDIR
	if (0 != chdir(path)) {
		LOGS(L_STORE,L_ERROR,("FATAL! chdir(%s) failed (%s)\n",
			path, strerror(errno)));
		*ptree = 0;
		return -1;
	}
	pm_snprintf(path, len, "%s", sha1_hexstr(sha1));
#else
	pm_snprintf(&path[plen], len - plen, "/%s", sha1_hexstr(sha1));
#endif


	*ptree = tree;
	return 0;
}

/*****************************************************************************
 *	store_put()
 *	Stores a buffer 'buff' of size CHUNKSIZE with a filename that is derived
 *	from the sha1 values. The path is built from the storepath and a
 *	up to two-level sub-directory consisting of nibbles of sha1.
 *****************************************************************************/
int store_put(const sha1_digest_t *sha1, const void *buff)
{
	const uint8_t *bytes = (const uint8_t *)buff;
	char filename[MAXPATHLEN];
	struct stat st;
	uint8_t fpr = 0;
	size_t size, tree, idx;
	int fd = -1, rc;
#if	TREE_CHDIR
	int home = -1;
#endif
	FUN("store_put");

#if	TREE_CHDIR
	if (-1 == (home = open(".", O_RDONLY))) {
		const char *errmsg = strerror(errno);
		LOGS(L_STORE,L_ERROR,("FATAL! open('.', O_RDONLY) call failed (%s)\n",
			errmsg));
		die(1, "open('.', O_RDONLY) failed (%s)", errmsg);
	}
#endif

	/* use SHA1 digest bytes 0 and 1 as an index */
	idx = sha1->digest[0] | ((uint32_t)sha1->digest[1] << 8);

	/* fingerprint index */
	fpr = keyroute(sha1);

	if (0 != (rc = store_path(sha1, filename, MAXPATHLEN, &tree))) {
		LOGS(L_STORE,L_ERROR,("FATAL! store_path() call failed (%s)\n",
			strerror(errno)));
		/* store this key as recently missing */
		g_store->missing[idx] = *sha1;
#if	TREE_CHDIR
		fchdir(home);
		close(home);
#endif
		errno = ENOENT;
		return -1;
	}

	/* strip off trailing zeroes */
	size = CHUNKSIZE - 1;
	while (size > 0 && 0 == bytes[size])
		size--;
	size++;
	
	LOGS(L_STORE,L_DEBUG,("put key %s (size %d) into file %s\n",
		sha1_hexstr(sha1), size, filename));

	/* check if the file was there */
	if (0 == stat(filename, &st) && S_ISREG(st.st_mode)) {
		STORE_LOCK();
		store_sub_key(sha1, st.st_size);
		STORE_UNLOCK();
	}
	fd = open(filename, O_RDWR|O_CREAT|O_TRUNC|O_BINARY, 0600);
	if (-1 == fd) {
		LOGS(L_STORE,L_ERROR,("FATAL! failed to create store file %s (%s)\n",
			filename, strerror(errno)));
#if	TREE_CHDIR
		fchdir(home);
		close(home);
#endif
		return -1;
	}

	if (size != (size_t)write(fd, buff, size)) {
		LOGS(L_STORE,L_ERROR,("FATAL! failed to write %d bytes to store file %s (%s)\n",
			size, filename, strerror(errno)));
		close(fd);
#if	TREE_CHDIR
		fchdir(home);
		close(home);
#endif
		return -1;
	}
	close(fd);
	fd = -1;
#if	TREE_CHDIR
	fchdir(home);
	close(home);
#endif

	STORE_LOCK();
	store_add_key(sha1, size);	
	STORE_UNLOCK();

	return 0;
}

/*****************************************************************************
 *	store_get()
 *	Fetches a buffer 'buff' of size CHUNKSIZE from a filename that is derived
 *	from the sha1 values. The path is built from the storepath and a
 *	up to two-level sub-directory consisting of nibbles of sha1.
 *	Returns -1 if the file does not exist or is not accessible.
 *****************************************************************************/
int store_get(const sha1_digest_t *sha1, void *buff)
{
	uint8_t *bytes = (uint8_t *)buff;
	char filename[MAXPATHLEN];
	struct stat st;
	int done;
	uint8_t fpr = 0;
	size_t idx, tree;
	int fd = -1, rc = 0;
#if	TREE_CHDIR
	int home = -1;
#endif
	FUN("store_get");

	/* use SHA1 digest bytes 0 and 1 as an index */
	idx = sha1->digest[0] | ((uint32_t)sha1->digest[1] << 8);

	/* quick check for recently missing keys */
	if (0 == memcmp(&g_store->missing[idx], sha1, SHA1SIZE)) {
		LOGS(L_STORE,L_DEBUGX,("missing key #%04x %s\n",
			idx, sha1_hexstr(sha1)));
		errno = ENOENT;
		return -1;
	}

	/* quick check for recently available keys */
	if (NULL == buff &&
		0 == memcmp(&g_store->available[idx], sha1, SHA1SIZE)) {
		LOGS(L_STORE,L_DEBUGX,("available key #%04x %s\n",
			idx, sha1_hexstr(sha1)));
		return 0;
	}

#if	TREE_CHDIR
	if (-1 == (home = open(".", O_RDONLY))) {
		const char *errmsg = strerror(errno);
		LOGS(L_STORE,L_ERROR,("FATAL! open('.', O_RDONLY) call failed (%s)\n",
			errmsg));
		die(1, "open('.', O_RDONLY) failed (%s)", errmsg);
	}
#endif

	/* fingerprint index */
	fpr = keyroute(sha1);

	if (0 != (rc = store_path(sha1, filename, MAXPATHLEN, &tree))) {
		LOGS(L_STORE,L_ERROR,("FATAL! store_path() call failed (%s)\n",
			strerror(errno)));
		/* set a missing[] entry for this index */
		g_store->missing[idx] = *sha1;
		/* reset available[] entry for this index */
		g_store->available[idx] = null;
#if	TREE_CHDIR
		fchdir(home);
		close(home);
#endif
		errno = ENOENT;
		return -1;
	}

	if (-1 == (rc = stat(filename, &st)) || !S_ISREG(st.st_mode)) {
		LOGS(L_STORE,L_MINOR,("file %s not found\n", filename));
		/* set a missing[] entry for this index */
		g_store->missing[idx] = *sha1;
		/* reset available[] entry for this index */
		g_store->available[idx] = null;
#if	TREE_CHDIR
		fchdir(home);
		close(home);
#endif
		errno = ENOENT;
		return -1;
	}

	if (NULL == buff) {
		/* reset a missing[] entry for this index */
		g_store->missing[idx] = null;
		/* set available[] entry for this index */
		g_store->available[idx] = *sha1;
		/* key is in the store, return zero */
#if	TREE_CHDIR
		fchdir(home);
		close(home);
#endif
		return 0;
	}

	fd = open(filename, O_RDONLY|O_BINARY);
	if (-1 == fd) {
		LOGS(L_STORE,L_DEBUG,("key %s file %s not found (%s)\n",
			sha1_hexstr(sha1), filename, strerror(errno)));
		errno = ENOENT;
		/* set a missing[] entry for this index */
		g_store->missing[idx] = *sha1;
		/* reset available[] entry for this index */
		g_store->available[idx] = null;
#if	TREE_CHDIR
		fchdir(home);
		close(home);
#endif
		return -1;
	}
	done = read(fd, buff, CHUNKSIZE);
#if	HAVE_FUTIMES
	if (0 != (rc = futimes(fd, NULL))) {
		LOGS(L_STORE,L_ERROR,("FATAL! futimes(%d,...) call failed (%s)\n",
			fd, strerror(errno)));
	}
	close(fd);
	fd = -1;
#else
	close(fd);
	fd = -1;
	if (0 != (rc = utimes(filename, NULL))) {
		LOGS(L_STORE,L_ERROR,("FATAL! utimes(%s,...) call failed (%s)\n",
			filename, strerror(errno)));
	}
#endif
#if	TREE_CHDIR
	fchdir(home);
	close(home);
#endif
	if (done < 0) {
		LOGS(L_STORE,L_ERROR,("FATAL! failed to read store file %s; size = %d (%s)\n",
			filename, done, strerror(errno)));
		return -1;
	}
	if (done < CHUNKSIZE) {
		/* pad trailing zeroes */
		memset(&bytes[done], 0, CHUNKSIZE - done);
	}
	/* reset a missing[] entry for this index */
	g_store->missing[idx] = null;
	/* set available[] entry for this index */
	g_store->available[idx] = *sha1;

	return 0;
}

/*****************************************************************************
 *	store_commit()
 *	Delete the file with a name that is derived from the sha1 values.
 *	The path is built from the storepath and a up to two-level
 *	sub-directory consisting of nibbles of sha1.
 *****************************************************************************/
static int store_commit(const sha1_digest_t *sha1, size_t size)
{
	char filename[MAXPATHLEN];
	uint8_t fpr = 0;
	size_t idx, tree = 0;
	int rc = 0;
	FUN("store_commit");

	/* use SHA1 digest bytes 0 and 1 as an index */
	idx = sha1->digest[0] | ((uint32_t)sha1->digest[1] << 8);

	/* quick check for recently missing keys */
	if (0 == memcmp(&g_store->missing[idx], sha1, SHA1SIZE)) {
		LOGS(L_STORE,L_DEBUGX,("missing key #%04x %s\n",
			idx, sha1_hexstr(sha1)));
		errno = ENOENT;
		return -1;
	}

	/* fingerprint index */
	fpr = keyroute(sha1);

	if (0 != (rc = store_path(sha1, filename, MAXPATHLEN, &tree))) {
		LOGS(L_STORE,L_ERROR,("FATAL! store_path() call failed (%s)\n",
			strerror(errno)));
		errno = ENOENT;
		return -1;
	}

	if (-1 == (rc = unlink(filename))) {
		LOGS(L_STORE,L_DEBUG,("unlink(%s) failed (%s)\n",
			filename, strerror(errno)));
		return -1;
	} 

	store_sub_key(sha1, size);

	LOGS(L_STORE,L_DEBUG,("key %s deleted (%d bytes)\n",
		sha1_hexstr(sha1), size));

	return 0;
}

#if	STORE_QSORT
/*****************************************************************************
 *	store_sort_drop_time()
 *	Return an index for the comparison of the 'time' fields from two
 *	drop_key_t entries, i.e. let qsort sort the drop[] array by time.
 *****************************************************************************/
static int store_sort_drop_time(const void *p1, const void *p2)
{
	const drop_key_t *d1 = (const drop_key_t *)p1;
	const drop_key_t *d2 = (const drop_key_t *)p2;
	return d1->time - d2->time;
}
#endif

/*****************************************************************************
 *	store_del()
 *	Enter a key into the list of pending deletes (drop key list).
 *	If the list is full, delete the earliest key now, sort the list by
 *	time (in case we would use varying timeouts) and make room for one
 *	new entry. Afterwards, commit all pending deletes that expired.
 *****************************************************************************/
int store_del(const sha1_digest_t *sha1)
{
	char filename[MAXPATHLEN];
	struct stat st;
	size_t i, j, idx, tree;
	drop_key_t *d;
	time_t t0;
	int rc = 0;
#if	TREE_CHDIR
	int home = -1;
#endif
	FUN("store_del");

	if (NULL == sha1) {
		LOGS(L_STORE,L_ERROR,("sha1 is NULL\n"));
		errno = EINVAL;
		return -1;
	}

#if	TREE_CHDIR
	if (-1 == (home = open(".", O_RDONLY))) {
		const char *errmsg = strerror(errno);
		LOGS(L_STORE,L_ERROR,("FATAL! open('.', O_RDONLY) call failed (%s)\n",
			errmsg));
		die(1, "open('.', O_RDONLY) failed (%s)", errmsg);
	}
#endif

	STORE_LOCK();
	/* first check if this delete is already pending */
	for (i = g_store->tail; i != g_store->head; i = (i + 1) % DROP_MAX) {
		d = &g_store->drop[i];
		if (0 == memcmp(&d->sha1, sha1, SHA1SIZE)) {
			STORE_UNLOCK();
#if	TREE_CHDIR
			fchdir(home);
			close(home);
#endif
			return 0;
		}
	}
	STORE_UNLOCK();

	/* use SHA1 digest bytes 0 and 1 as an index */
	idx = sha1->digest[0] | ((uint32_t)sha1->digest[1] << 8);

	if (0 != (rc = store_path(sha1, filename, MAXPATHLEN, &tree))) {
		LOGS(L_STORE,L_ERROR,("FATAL! store_path() call failed (%s)\n",
			strerror(errno)));
#if	TREE_CHDIR
		fchdir(home);
		close(home);
#endif
		errno = EIO;
		return -1;
	}

	if (-1 == (rc = stat(filename, &st)) || !S_ISREG(st.st_mode)) {
		LOGS(L_STORE,L_DEBUG,("key %s not found\n",
			sha1_hexstr(sha1)));
		/* This key is missing now */
		g_store->missing[idx] = *sha1;
#if	TREE_CHDIR
		fchdir(home);
		close(home);
#endif
		errno = ENOENT;
		return -1;
	}

	STORE_LOCK();
	/* if we cannot simply add another drop key entry */
	if ((g_store->head + 1) % DROP_MAX == g_store->tail) {
		LOGS(L_STORE,L_MINOR,("list is full: committing %d pending deletes\n",
			DROP_MAX/8));
#if	STORE_QSORT
		/* sort by drop time -- earliest first */
		qsort(g_store->drop, DROP_MAX, sizeof(drop_key_t),
			store_sort_drop_time);
		g_store->tail = 0;
		g_store->head = DROP_MAX - 1;
#endif
		/* now drop the earliest DROP_MAX/8 keys */
		for (i = g_store->tail, j = 0; j < DROP_MAX/8; j++) {
			d = &g_store->drop[i];
			LOGS(L_STORE,L_DEBUG,("committing key %s delete due %s\n",
				sha1_hexstr(&d->sha1),
				datetime_str(d->time)));
			if (0 != (rc = store_commit(&d->sha1, d->size))) {
				LOGS(L_STORE,L_DEBUG,("committing failed (%s)\n",
					strerror(errno)));
			}
			i = (i + 1) % DROP_MAX;
		}

		/* new tail after committing 'j' deletes */
		g_store->tail = i;

		LOGS(L_STORE,L_MINOR,("removed %d entries; list has %d entries now\n",
			j,
			g_store->head >= g_store->tail ?
				g_store->head - g_store->tail :
				g_store->head + DROP_MAX - g_store->tail));
	}

	t0 = time(NULL);

	/* enter this key in the head slot */
	d = &g_store->drop[g_store->head];
	g_store->head = (g_store->head + 1) % DROP_MAX;
	d->sha1 = *sha1;
	d->time = t0 + 180;	/* nuke in 180 seconds = 3 minutes from now */
	d->size = st.st_size;
	LOGS(L_STORE,L_DEBUG,("appended key drop %s (%d bytes) at %s\n",
		sha1_hexstr(&d->sha1),
		d->size, datetime_str(d->time)));

	/* now commit keys which expired their timeout */
	for (i = g_store->tail, j = 0; i != g_store->head; j++) {
		d = &g_store->drop[i];
		if (d->time > t0) {
			break;
		}
		LOGS(L_STORE,L_DEBUG,("committing key %s delete due %s\n",
			sha1_hexstr(&d->sha1),
			datetime_str(d->time)));
		if (0 != (rc = store_commit(&d->sha1, d->size))) {
			LOGS(L_STORE,L_DEBUG,("committing failed (%s)\n",
				strerror(errno)));
		}
		i = (i + 1) % DROP_MAX;
	}

	/* committed some keys? */
	if (j > 0) {
		g_store->tail = i;
		LOGS(L_STORE,L_MINOR,("removed %d entries; list has %d entries now\n",
			j,
			g_store->head >= g_store->tail ?
				g_store->head - g_store->tail :
				g_store->head + DROP_MAX - g_store->tail));
	}
	
	STORE_UNLOCK();
#if	TREE_CHDIR
	fchdir(home);
	close(home);
#endif
	return 0;
}

/*****************************************************************************
 *	store_zap()
 *	Immediately zap a key from the store.
 *****************************************************************************/
int store_zap(const sha1_digest_t *sha1)
{
	size_t size = CHUNKSIZE;
	uint8_t *buff = xmalloc(size);
	int rc = 0;
#if	TREE_CHDIR
	int home = -1;
#endif
	FUN("store_zap");

	if (NULL == sha1) {
		LOGS(L_STORE,L_ERROR,("sha1 is NULL\n"));
		errno = EINVAL;
		return -1;
	}

	if (0 != (rc = store_get(sha1, buff))) {
		LOGS(L_STORE,L_MINOR,("key %s is already gone\n",
			sha1_hexstr(sha1)));
		xfree(buff);
		errno = ENOENT;
		return -1;
	}
	while (size > 0 && 0x00 == buff[size-1])
		size--;
	xfree(buff);

#if	TREE_CHDIR
	if (-1 == (home = open(".", O_RDONLY))) {
		const char *errmsg = strerror(errno);
		LOGS(L_STORE,L_ERROR,("FATAL! open('.', O_RDONLY) call failed (%s)\n",
			errmsg));
		die(1, "open('.', O_RDONLY) failed (%s)", errmsg);
	}
#endif
	STORE_LOCK();
	rc = store_commit(sha1, size);
	STORE_UNLOCK();
#if	TREE_CHDIR
	fchdir(home);
	close(home);
#endif

	return rc;
}

/*****************************************************************************
 *	store_check()
 *	Check if 'required' of 'count' keys specified in '*sha1' that are marked
 *	(non-zero bit) in flags are available in the store.
 *****************************************************************************/
int store_check(const sha1_digest_t *sha1, int flags, size_t count, size_t required)
{
	size_t i, have = 0;
	FUN("store_check");

	for (i = 0; i < count; i++) {
		if (0 == (flags & (1 << i))) {
			have++;
		} else if (0 == store_get(&sha1[i], NULL)) {
			have++;
		}
	}
	if (have < required) {
		/* at least one is missing */
		errno = ENOENT;
		return -1;
	}
	return 0;
}

/*
 *	store_sort_age_dist()
 *	Return an index for the position of keys sorted by age and/or
 *	their distance from our optimal fingerprint.
 */
static int store_sort_age_dist(const void *p1, const void *p2)
{
	const fileage_t *a1 = (const fileage_t *)p1;
	const fileage_t *a2 = (const fileage_t *)p2;
	int ad1, ad2;
	/* For keys younger than a week, don't consider the distance */
	if (a1->age < 7 * 86400 || a2->age < 7 * 86400) {
		ad1 = a1->age;
		ad2 = a2->age;
	} else {
		/* else weigh the distance as if 255 were approx. 192 days old */
		ad1 = (int)(((uint64_t)a1->dist * 65535 + a1->age) / 65536);
		ad2 = (int)(((uint64_t)a2->dist * 65535 + a2->age) / 65536);
	}
	return ad2 - ad1;
}

/*
 *	store_sort_treepos()
 *	Return an index for the position inside the tree of directories,
 *	lower numbers come first.
 */
static int store_sort_treepos(const void *p1, const void *p2)
{
	const fileage_t *a1 = (const fileage_t *)p1;
	const fileage_t *a2 = (const fileage_t *)p2;

	if (a1->tree1 == a2->tree1) {
		if (a1->tree2 == a2->tree2) {
			return a1->tree3 - a2->tree3;
		}
		return a1->tree2 - a2->tree2;
	}
	return a1->tree1 - a2->tree1;
}

/*
 *	hex2sha1()
 *	Convert a 2*SHA1SIZE string of hex digits into the SHA1
 *	field of a chkey_t.
 */
static int hex2sha1(sha1_digest_t *sha1, const char *src)
{
	size_t i;

	memset(sha1, 0, sizeof(*sha1));

	for (i = 0; i < 2 * SHA1SIZE; i++, src++) {
		switch (*src) {
		case '0': case '1': case '2': case '3': case '4':
		case '5': case '6': case '7': case '8': case '9':
			sha1->digest[i/2] |= *src - '0';
			break;
		case 'A': case 'B': case 'C': case 'D': case 'E': case 'F':
			sha1->digest[i/2] |= *src - 'A' + 10;
			break;
		case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
			sha1->digest[i/2] |= *src - 'a' + 10;
			break;
		default:
			errno = EINVAL;
			return -1;
		}
		if (0 == (i % 2)) {
			sha1->digest[i/2] *= 16;
		}
		if ('\0' == *src) {
			break;
		}
	}

	if (2*SHA1SIZE == i) {
		return 0;
	}

	errno = EINVAL;
	return -1;
}

/*
 *	store_purge()
 *	Whenever the store size overflows the specified limit, start a
 *	'garbage' collection and throw away outdated or badly matching keys.
 */
int store_purge(void)
{
#if	TREE_CHDIR
	char cwd[MAXPATHLEN];
#endif
	char path[MAXPATHLEN];
	char file[MAXPATHLEN];
	fileage_t *list;
	size_t i, count, limit, deletes;
	uint64_t cur_watermark, low_watermark;
	uint8_t tree1, tree2, tree3, fpr;
	time_t t0;
	DIR *dir;
	struct dirent *de;
	struct stat st;
	int rc;
	FUN("store_purge");

	if (g_store->currsize < g_store->storesize) {
		LOGS(L_STORE,L_NORMAL,("*** nothing to do: currsize %uMB < storesize %uMB\n",
			(unsigned)(g_store->currsize / 1024 / 1024),
			(unsigned)(g_store->storesize / 1024 / 1024)));
		return 0;
	}
	LOGS(L_STORE,L_NORMAL,("*** purging store: currsize %uMB > storesize %uMB\n",
		(unsigned)(g_store->currsize / 1024 / 1024),
		(unsigned)(g_store->storesize / 1024 / 1024)));

#if	TREE_CHDIR
	if (NULL == getcwd(cwd, sizeof(cwd))) {
		LOGS(L_STORE,L_NORMAL,("*** getcwd() failed (%s)\n",
			strerror(errno)));
		die(1,"getcwd() call failed\n");
	}
#endif

	/* base purging on current time */
	t0 = time(NULL);

	/* allocate a list to hold filenames and ages; leave some slack */
	limit = g_store->storecount + 1024;
	list = (fileage_t *)xcalloc(limit, sizeof(fileage_t));
	count = 0;

	switch (g_conf->storedepth) {
	case 1:
		/* scan the 1 level tree and stat the files */
		for (tree1 = 0; tree1 < 16; tree1++) {
			pm_snprintf(path, MAXPATHLEN, "%s/%x",
					g_conf->storepath, tree1);
#if	TREE_CHDIR
			if (0 != chdir(path)) {
				LOGS(L_STORE,L_NORMAL,("*** chdir('%s') failed (%s)\n",
					path, strerror(errno)));
				die(1,"chdir('%s') call failed\n", path);
			}
			dir = opendir(".");
#else
			dir = opendir(path);
#endif
			if (NULL == dir) {
				continue;
			}
			STORE_LOCK();
			LOGS(L_STORE,L_NORMAL,("** scanning %s\n", path));
			while (NULL != (de = readdir(dir))) {
				if (count >= limit) {
					/* the list is full... */
					break;
				}
				if (2*SHA1SIZE != strlen(de->d_name)) {
					continue;
				}
				pm_snprintf(file, sizeof(file),
					"%s/%s", path, de->d_name);
				if (0 != stat(file, &st) || !S_ISREG(st.st_mode)) {
					/* cannot stat or is not a regular file */
					continue;
				}
				if (st.st_size > CHUNKSIZE) {
					LOGS(L_STORE,L_NORMAL,("*** invalid key size %s (%#x)\n",
						file, (unsigned)st.st_size));
					unlink(file);
					continue;
				}
				/* get fingerprint index */
				hex2sha1(&list[count].sha1, de->d_name);
				fpr = keyroute(&list[count].sha1);
				/* distance to current (0 = keep to 255 = trash) */
				list[count].dist = 255 - g_store->fingerprint[fpr];
				list[count].tree1 = tree1;
				list[count].tree2 = 0;
				list[count].tree3 = 0;
				list[count].fpr = fpr;
				list[count].age = (t0 > st.st_mtime) ? t0 - st.st_mtime : 0;
				list[count].size = st.st_size;
				count++;
			}
			closedir(dir);
			STORE_UNLOCK();
		}
		break;

	case 2:
		/* scan the 2 level tree and stat the files */
		for (tree1 = 0; tree1 < 16; tree1++) {
			for (tree2 = 0; tree2 < 16; tree2++) {
				pm_snprintf(path, MAXPATHLEN, "%s/%x/%x",
					g_conf->storepath, tree1, tree2);
#if	TREE_CHDIR
				if (0 != chdir(path)) {
					LOGS(L_STORE,L_NORMAL,("*** chdir('%s') failed (%s)\n",
						path, strerror(errno)));
					die(1,"chdir('%s') call failed\n", path);
				}
				dir = opendir(".");
#else
				dir = opendir(path);
#endif
				if (NULL == dir) {
					continue;
				}
				STORE_LOCK();
				LOGS(L_STORE,L_NORMAL,("** scanning %s\n", path));
				while (NULL != (de = readdir(dir))) {
					if (count >= limit) {
						/* the list is full... */
						break;
					}
					if (2*SHA1SIZE != strlen(de->d_name)) {
						continue;
					}
					pm_snprintf(file, sizeof(file),
						"%s/%s", path, de->d_name);
					if (0 != stat(file, &st) || !S_ISREG(st.st_mode)) {
						/* cannot stat or is not a regular file */
						continue;
					}
					if (st.st_size > CHUNKSIZE) {
						LOGS(L_STORE,L_NORMAL,("*** invalid key size %s (%#x)\n",
							file, (unsigned)st.st_size));
						unlink(file);
						continue;
					}
					/* get fingerprint index */
					hex2sha1(&list[count].sha1, de->d_name);
					fpr = keyroute(&list[count].sha1);
					/* distance to current (0 = keep to 255 = trash) */
					list[count].dist = 255 - g_store->fingerprint[fpr];
					list[count].tree1 = tree1;
					list[count].tree2 = tree2;
					list[count].tree3 = 0;
					list[count].fpr = fpr;
					list[count].age = (t0 > st.st_mtime) ? t0 - st.st_mtime : 0;
					list[count].size = st.st_size;
					count++;
				}
				closedir(dir);
				STORE_UNLOCK();
			}
		}
		break;

	case 3:
		/* scan the 3 level tree and stat the files */
		for (tree1 = 0; tree1 < 16; tree1++) {
			for (tree2 = 0; tree2 < 16; tree2++) {
				for (tree3 = 0; tree3 < 16; tree3++) {
					pm_snprintf(path, MAXPATHLEN, "%s/%x/%x/%x",
						g_conf->storepath, tree1, tree2, tree3);
#if	TREE_CHDIR
					if (0 != chdir(path)) {
						LOGS(L_STORE,L_NORMAL,("*** chdir('%s') failed (%s)\n",
							path, strerror(errno)));
						die(1,"chdir('%s') call failed\n", path);
					}
					dir = opendir(".");
#else
					dir = opendir(path);
#endif
					if (NULL == dir) {
						continue;
					}
					STORE_LOCK();
					LOGS(L_STORE,L_NORMAL,("** scanning %s\n", path));
					while (NULL != (de = readdir(dir))) {
						if (count >= limit) {
							/* the list is full... */
							break;
						}
						if (2*SHA1SIZE != strlen(de->d_name)) {
							continue;
						}
						pm_snprintf(file, sizeof(file),
							"%s/%s", path, de->d_name);
						if (0 != stat(file, &st) || !S_ISREG(st.st_mode)) {
							/* cannot stat or is not a regular file */
							continue;
						}
						if (st.st_size > CHUNKSIZE) {
							LOGS(L_STORE,L_NORMAL,("*** invalid key size %s (%#x)\n",
								file, (unsigned)st.st_size));
							unlink(file);
							continue;
						}
						/* get fingerprint index */
						hex2sha1(&list[count].sha1, de->d_name);
						fpr = keyroute(&list[count].sha1);
						/* distance to current (0 = keep to 255 = trash) */
						list[count].dist = 255 - g_store->fingerprint[fpr];
						list[count].tree1 = tree1;
						list[count].tree2 = tree2;
						list[count].tree3 = tree3;
						list[count].fpr = fpr;
						list[count].age = (t0 > st.st_mtime) ?
							t0 - st.st_mtime : 0;
						list[count].size = st.st_size;
						count++;
					}
					closedir(dir);
					STORE_UNLOCK();
				}
			}
		}
		break;

	default:
		/* scan the storepath and stat the files */
		strncpy(path, g_conf->storepath, MAXPATHLEN);
#if	TREE_CHDIR
		if (0 != chdir(path)) {
			LOGS(L_STORE,L_NORMAL,("*** chdir('%s') failed (%s)\n",
				path, strerror(errno)));
			die(1,"chdir('%s') call failed\n", path);
		}
		dir = opendir(".");
#else
		dir = opendir(path);
#endif
		if (NULL != dir) {
			STORE_LOCK();
			LOGS(L_STORE,L_NORMAL,("** scanning %s\n", path));
			while (NULL != (de = readdir(dir))) {
				if (count >= limit) {
					/* the list is full... */
					break;
				}
				if (2*SHA1SIZE != strlen(de->d_name)) {
					continue;
				}
				pm_snprintf(file, sizeof(file),
					"%s/%s", path, de->d_name);
				if (0 != stat(file, &st) || !S_ISREG(st.st_mode)) {
					/* cannot stat or is not a regular file */
					continue;
				}
				if (st.st_size > CHUNKSIZE) {
					LOGS(L_STORE,L_NORMAL,("*** invalid key size %s (%#x)\n",
						file, (unsigned)st.st_size));
					unlink(file);
					continue;
				}
				/* get fingerprint index */
				hex2sha1(&list[count].sha1, de->d_name);
				fpr = keyroute(&list[count].sha1);
				/* distance to current (0 = keep to 255 = trash) */
				list[count].dist = 255 - g_store->fingerprint[fpr];
				list[count].tree1 = 0;
				list[count].tree2 = 0;
				list[count].tree3 = 0;
				list[count].fpr = fpr;
				list[count].age = (t0 > st.st_mtime) ? t0 - st.st_mtime : 0;
				list[count].size = st.st_size;
				count++;
			}
			closedir(dir);
			STORE_UNLOCK();
		}
	}
#if	TREE_CHDIR
	if (0 != chdir(cwd)) {
		LOGS(L_STORE,L_NORMAL,("*** chdir('%s') failed (%s)\n",
			cwd, strerror(errno)));
		die(1,"chdir('%s') call failed\n", cwd);
	}
#endif

	/* now sort the list by fingerprint distance and age */
	qsort(list, count, sizeof(fileage_t), store_sort_age_dist);

	/* remove 5% of the keys */
	low_watermark = g_store->storesize * 95 / 100;
	cur_watermark = g_store->currsize;

	/* start marking files to be purged until we are below the watermark */
	for (i = 0, deletes = 0; i < count; i++) {
		fileage_t *fa = &list[i];

		/* mark this file to be purged */
		fa->marked = 1;
		cur_watermark -= fa->size;
		deletes += 1;

		if (cur_watermark < low_watermark)
			break;
	}

	LOGS(L_STORE,L_NORMAL,("*** purging store: %d keys to delete\n", deletes));

	/* now sort the file list in tree order */
	qsort(list, count, sizeof(fileage_t), store_sort_treepos);
	
	STORE_LOCK();
	for (i = 0; i < count; i++) {
		fileage_t *fa = &list[i];

		/* Continue if this file is not marked */
		if (0 == fa->marked)
			continue;

		if (0 != (rc = store_commit(&fa->sha1, fa->size))) {
			LOGS(L_STORE,L_ERROR,("deleting key %s failed\n",
				sha1_hexstr(&fa->sha1)));
		}

		--deletes;
		/* every 1024 files go to sleep for 10ms */
		if (0 == (deletes % 1024)) {
			STORE_UNLOCK();
			LOGS(L_STORE,L_NORMAL,("*** %d to go\n", deletes));
			osd_usleep(10000);
			STORE_LOCK();
		}
	}
	STORE_UNLOCK();

	xfree(list);

	return 0;
}

void store_exit(int sig)
{
	FUN("store_exit");

	signal(sig, SIG_DFL);
	LOGS(L_STORE,L_MINOR,("*** {%d} signal %s ***\n",
		(int)getpid(), signal_name(sig)));
	osd_exit(sig);
}

int store_scandir(DIR *dir, int zap)
{
	struct dirent *de;
	struct stat st;
	sha1_digest_t sha1;
	size_t tree, size;
	uint8_t fpr;
	int rc;
	FUN("store_scandir");

	STORE_LOCK();
	while (NULL != (de = readdir(dir))) {

		if (0 == strcmp(de->d_name, ".") ||
			0 == strcmp(de->d_name, "..")) {
			continue;
		}

		if (0 != zap) {
			unlink(de->d_name);
			continue;
		}

		if (0 != stat(de->d_name, &st) || !S_ISREG(st.st_mode)) {
			LOGS(L_STORE,L_ERROR,("stat(%s,...) failed (%s)\n",
				de->d_name, strerror(errno)));
			continue;
		}
		if (S_ISDIR(st.st_mode)) {
			LOGS(L_STORE,L_DEBUG,("skipping directory %s\n",
				de->d_name));
			continue;
		}
		if (!S_ISREG(st.st_mode)) {
			LOGS(L_STORE,L_DEBUG,("skipping non-file %s\n",
				de->d_name));
			continue;
		}

		rc = hex2sha1(&sha1, de->d_name);
		if (0 != rc) {
			LOGS(L_STORE,L_NORMAL,("unlinking illegal filename %s\n",
				de->d_name));
			unlink(de->d_name);
			continue;
		}
		if (0 == st.st_size) {
			LOGS(L_STORE,L_NORMAL,("unlinking zero length file %s\n",
				de->d_name));
			unlink(de->d_name);
			continue;
		}
		if (st.st_size > CHUNKSIZE) {
			LOGS(L_STORE,L_NORMAL,("unlinking invalid length file %s (%#x)\n",
				de->d_name, (unsigned)st.st_size));
			unlink(de->d_name);
			continue;
		}

		/* extract routing key */
		fpr = keyroute(&sha1);
		switch (g_conf->storedepth) {
		case 1:
			tree = sha1.digest[SHA1SIZE - 2] / 16;
			break;
		case 2:
			tree = sha1.digest[SHA1SIZE - 2];
			break;
		default:
			tree = 0;
		}
		size = st.st_size;
		g_store->keycount[fpr] += 1;
		g_store->currsize += size;
		g_store->storecount += 1;
	}

	STORE_UNLOCK();
	return 0;
}

int store(void)
{
	char path[MAXPATHLEN];
	uint8_t tree1, tree2, tree3;
	DIR *dir;
	size_t size;
	int home = -1;
	int zap = 0;
	int rc = 0;
	FUN("store");

	/* capture signals */
	set_signal_handler(SIGHUP, store_exit);
	set_signal_handler(SIGINT, store_exit);
	set_signal_handler(SIGPIPE, store_exit);
	set_signal_handler(SIGALRM, store_exit);
	set_signal_handler(SIGTERM, store_exit);

	size = sizeof(store_t);
	g_store = (store_t *)scalloc(size, 1);
	if (NULL == g_store) {
		LOGS(L_STORE,L_ERROR,("failed to scalloc() store; size %d (%s)\n",
			size, strerror(errno)));
		return -1;
	}

	if (0 != (rc = osd_sem_init(&g_store->sem, 1, 1))) {
		LOGS(L_STORE,L_ERROR,("osd_sem_init(0x%x,%d,%d) call failed (%s)\n",
			(unsigned)&g_store->sem, 1, 1, strerror(errno)));
		return -1;
	}

	g_store->storesize = g_conf->storesize;
	if (g_conf->storedepth > 3) {
		LOGS(L_STORE,L_NORMAL,("storedepth clipped from %u to 3\n",
			(unsigned)g_conf->storedepth));
		g_conf->storedepth = 3;
	}

	if (-1 == (home = open(".", O_RDONLY))) {
		const char *errmsg = strerror(errno);
		LOGS(L_STORE,L_ERROR,("FATAL! open('.', O_RDONLY) call failed (%s)\n",
			errmsg));
		die(1, "open('.', O_RDONLY) failed (%s)", errmsg);
	}

	if (0 != chdir(g_conf->storepath)) {
		if (0 != mkdir(g_conf->storepath, 0700)) {
			LOGS(L_STORE,L_NORMAL,("*** mkdir('%s') failed (%s)\n",
				g_conf->storepath, strerror(errno)));
			die(1,"mkdir('%s') call failed\n", g_conf->storepath);
		}
		if (0 != chdir(g_conf->storepath)) {
			LOGS(L_STORE,L_NORMAL,("*** chdir('%s') failed (%s)\n",
				g_conf->storepath, strerror(errno)));
			die(1,"chdir('%s') call failed\n", g_conf->storepath);
		}
	}

	zap = store_get_version();

	info("  0%%\b\b\b\b");
	if (g_conf->storedepth == 1) {
		/* scan the 1 level tree files and read the keys */
		for (tree1 = 0; tree1 < 16; tree1++) {
			pm_snprintf(path, MAXPATHLEN, "%s/%x",
				g_conf->storepath, tree1);
			if (0 != chdir(path)) {
				if (0 != mkdir(path, 0700)) {
					LOGS(L_STORE,L_NORMAL,("*** mkdir('%s') failed (%s)\n",
						path, strerror(errno)));
					die(1,"mkdir('%s') call failed\n", path);
				}
				if (0 != chdir(path)) {
					LOGS(L_STORE,L_NORMAL,("*** chdir('%s') failed (%s)\n",
						path, strerror(errno)));
					die(1,"chdir('%s') call failed\n", path);
				}
			}
			dir = opendir(".");
			if (NULL != dir) {
				store_scandir(dir, zap);
				closedir(dir);
			}
			info("%3d%%\b\b\b\b", (tree1 + 1) * 100 / 16);
		}
	} else if (g_conf->storedepth == 2) {
		/* scan the 2 level tree files and read the keys */
		for (tree1 = 0; tree1 < 16; tree1++) {
			pm_snprintf(path, MAXPATHLEN, "%s/%x",
				g_conf->storepath, tree1);
			if (0 != chdir(path)) {
				if (0 != mkdir(path, 0700)) {
					LOGS(L_STORE,L_NORMAL,("*** mkdir('%s') failed (%s)\n",
						path, strerror(errno)));
					die(1,"mkdir('%s') call failed\n", path);
				}
			}
			for (tree2 = 0; tree2 < 16; tree2++) {
				pm_snprintf(path, MAXPATHLEN, "%s/%x/%x",
					g_conf->storepath, tree1, tree2);
				if (0 != chdir(path)) {
					if (0 != mkdir(path, 0700)) {
						LOGS(L_STORE,L_NORMAL,("*** mkdir('%s') failed (%s)\n",
							path, strerror(errno)));
						die(1,"mkdir('%s') call failed\n", path);
					}
					if (0 != chdir(path)) {
						LOGS(L_STORE,L_NORMAL,("*** chdir('%s') failed (%s)\n",
							path, strerror(errno)));
						die(1,"chdir('%s') call failed\n", path);
					}
				}
				dir = opendir(".");
				if (NULL != dir) {
					store_scandir(dir, zap);
					closedir(dir);
				}
				info("%3d%%\b\b\b\b", ((tree1*16)+tree2+1) * 100 / 256);
			}
		}
	} else if (g_conf->storedepth == 3) {
		/* scan the 3 level tree files and read the keys */
		for (tree1 = 0; tree1 < 16; tree1++) {
			pm_snprintf(path, MAXPATHLEN, "%s/%x",
				g_conf->storepath, tree1);
			if (0 != chdir(path)) {
				if (0 != mkdir(path, 0700)) {
					LOGS(L_STORE,L_NORMAL,("mkdir('%s') failed (%s)\n",
						path, strerror(errno)));
					die(1,"mkdir('%s') call failed\n", path);
				}
			}
			for (tree2 = 0; tree2 < 16; tree2++) {
				pm_snprintf(path, MAXPATHLEN, "%s/%x/%x",
					g_conf->storepath, tree1, tree2);
				if (0 != chdir(path)) {
					if (0 != mkdir(path, 0700)) {
						LOGS(L_STORE,L_NORMAL,("mkdir('%s') failed (%s)\n",
							path, strerror(errno)));
						die(1,"mkdir('%s') call failed\n", path);
					}
				}
				for (tree3 = 0; tree3 < 16; tree3++) {
					pm_snprintf(path, MAXPATHLEN, "%s/%x/%x/%x",
						g_conf->storepath, tree1, tree2, tree3);
					if (0 != chdir(path)) {
						if (0 != mkdir(path, 0700)) {
							LOGS(L_STORE,L_NORMAL,("mkdir('%s') failed (%s)\n",
								path, strerror(errno)));
							die(1,"mkdir('%s') call failed\n", path);
						}
					}
					dir = opendir(".");
					if (NULL != dir) {
						store_scandir(dir, zap);
						closedir(dir);
					}
					info("%3d%%\b\b\b\b", (tree1*256+tree2*16+tree3+1) *
						100 / 4096);
				}
			}
		}
	} else {
		/* scan the storepath files and read the keys */
		strncpy(path, g_conf->storepath, MAXPATHLEN);
		if (0 != chdir(path)) {
			if (0 != mkdir(path, 0700)) {
				LOGS(L_STORE,L_NORMAL,("*** mkdir('%s') failed (%s)\n",
					path, strerror(errno)));
				die(1,"mkdir('%s') call failed\n", path);
			}
			if (0 != chdir(path)) {
				LOGS(L_STORE,L_NORMAL,("*** chdir('%s') failed (%s)\n",
					path, strerror(errno)));
				die(1,"chdir('%s') call failed\n", path);
			}
		}
		dir = opendir(".");
		if (NULL != dir) {
			store_scandir(dir, zap);
			closedir(dir);
		}
		info("100%%\b\b\b\b");
	}

	if (0 != fchdir(home)) {
		LOGS(L_STORE,L_NORMAL,("*** fchdir(%d) failed (%s)\n",
			home, strerror(errno)));
		die(1,"fchdir(%d) call failed\n", home);
	}
	close(home);

	if (0 != (rc = store_put_version(zap))) {
		return rc;
	}

	if (0 == zap) {
		info("purge\b\b\b\b\b");
		store_purge();
	}

	store_upd_fingerprint();
	LOGS(L_STORE,L_NORMAL,("Opened %uMB [%uMB] %d-level store with %d keys\n",
		(unsigned)(g_store->currsize / 1024 / 1024),
		(unsigned)(g_store->storesize / 1024 / 1024),
		g_conf->storedepth,
		g_store->storecount));
	info("%uMB [%uMB] %d-level, %d keys ",
		(unsigned)(g_store->currsize / 1024 / 1024),
		(unsigned)(g_store->storesize / 1024 / 1024),
		g_conf->storedepth,
		g_store->storecount);

	return rc;
}
